package org.example.Backtracking_algorithm;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class Total_combination_II {
    public static ArrayList<List<Integer>> arrayList = new ArrayList<>();
    public static LinkedList<Integer> value = new LinkedList<>();

    public static void main(String[] args) {
        //组合总和 II

        //给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
        //candidates 中的每个数字在每个组合中只能使用 一次 。
        //注意：解集不能包含重复的组合。
        int[] nums = {5, 4, 5, 1, 5, 3, 1, 4, 5, 5, 4};
        Arrays.sort(nums);
        for (int num : nums) {
            System.out.print(num + " ");
        }
        System.out.println();
        combinationSum2(nums, 10);
        prin();
    }

    public static List<List<Integer>> combinationSum2(int[] candidates, int target) {
        get(candidates, target, 0, 0);
        return arrayList;
    }

    public static void get(int[] candidates, int target, int sum, int index) {
        if (sum == target) {
            arrayList.add(new ArrayList<>(value));
            return;
        }
        for (int i = index; i < candidates.length; i++) {
            if (sum + candidates[i] > target) break;
            if (i > index && candidates[i] == candidates[i - 1]) continue;
            value.add(candidates[i]);
            sum += candidates[i];
            get(candidates, target, sum, i + 1);
            value.removeLast();
            sum -= candidates[i];
        }
    }

    public static void prin() {
        for (List<Integer> list : arrayList) {
            System.out.print("[ ");
            for (Integer integer : list) {
                System.out.print(integer);
            }
            System.out.print(" ]");
        }
        System.out.println();
    }
}
